package com.zzy.other;

/**
 * 1240. 铺瓷砖
 * 你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。
 * 房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。
 * 假设正方形瓷砖的规格不限，边长都是整数。
 * 请你帮设计师计算一下，最少需要用到多少块方形瓷砖？
 * <p>
 * 输入：n = 2, m = 3
 * 输出：3
 * 解释：3 块地砖就可以铺满卧室。
 * 2 块 1x1 地砖
 * 1 块 2x2 地砖
 */
public class L1240tilingRectangle {

    private int res;

    public int tilingRectangle(int n, int m) {
        boolean[][] tiled = new boolean[n][m];
        res = n * m;
        process(tiled, 0);
        return res;
    }

    /**
     * 铺瓷砖的过程
     *
     * @param tiled 待铺地板
     * @param count 已用瓷砖
     */
    private void process(boolean[][] tiled, int count) {
        //剪枝
        if (count > res) {
            return;
        }
        //找出第一个空地
        int[] emptyPos = findFirstEmpty(tiled);
        if (emptyPos[0] == -1 && emptyPos[1] == -1) {
            //todo 错误1，退出时没有计算结果
            res = Math.min(count,res);
            return;
        }
        //计算当前可容纳的最大的正方地砖
        int maxLen = Math.min(tiled.length - emptyPos[1], tiled[0].length - emptyPos[0]);
        for (int len = maxLen; len >= 1; len--) {
            if (setStatus(tiled, emptyPos[0], emptyPos[1], emptyPos[0] + len - 1, emptyPos[1] + len - 1, false)) {
                process(tiled, count + 1);
                setStatus(tiled, emptyPos[0], emptyPos[1], emptyPos[0] + len - 1, emptyPos[1] + len - 1, true);
            }
        }
    }

    /**
     * 用于改变铺地面的状态
     *
     * @param tiled  地面
     * @param x      起始横坐标
     * @param y      开始纵坐标
     * @param x1     结束横
     * @param y1     结束纵
     * @param status 必须保证该范围内的全为status，才能进行翻转状态
     * @return
     */
    private boolean setStatus(boolean[][] tiled, int x, int y, int x1, int y1, boolean status) {
        //todo 错误，没有正确的把所有格子该状态 =忘了
        for (int i = x; i <= x1; i++) {
            for (int j = y; j <= y1; j++) {
                if (tiled[i][j] != status) {
                    return false;
                }
            }
        }
        for (int i = x; i <= x1; i++) {
            for (int j = y; j <= y1; j++) {
                tiled[i][j] = !tiled[i][j];
            }
        }
        return true;
    }

    /**
     * 用于找出第一块空地
     *
     * @param tiled tiled
     * @return 坐标
     */
    private int[] findFirstEmpty(boolean[][] tiled) {
        for (int i = 0; i < tiled.length; i++) {
            for (int j = 0; j < tiled[0].length; j++) {
                if (!tiled[i][j]) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }


}
